The present invention relates to a decoding apparatus and a decoding method, which are used for decoding data completing a convolution encoding process, as well as relates to a data-receiving apparatus and a data-receiving method, which are used for receiving the decoding data completing the convolution encoding process.
Convolution encoding is one of correction-encoding technologies used in applications such as data communication. Convolution encoding is carried out sequentially.
FIG. 1 is a diagram showing a typical configuration of a convolution encoder having a constraint length of 4. The convolution encoder having a constraint length of 4 includes 3 delay elements (registers) 51, 52 and 53 in addition to a logic circuit 55. The logic circuit 55 carries out typically exclusive logical OR processing on at least some pieces of input data received from an input terminal 50 and of data output by the delay elements 51, 52 and 53. In the typical configuration shown in FIG. 1, the input data from the input terminal 50 and the data output by the delay element 53 are subjected to exclusive logical OR processing in an exclusive logical OR gate 55a, which outputs a result of the processing to an output terminal 56a. On the other hand, the pieces of data output by the delay elements 51 and 52 are subjected to exclusive logical OR processing in an exclusive logical OR gate 55b, which outputs a result of the processing to an output terminal 56b. In the typical configuration shown in FIG. 1, the encoding rate is 2 indicating that the convolution encoder has 2 outputs. However, the encoding rate can also be set at 3. In addition, the logic circuit 55 can be configured in a variety of ways.
Data obtained as a result of an encoding process carried out by such a convolution encoder is subjected to a maximum-likelihood decoding process for cumulating metrics of likelihood in accordance with a trellis diagram or a state-transition diagram and selecting a path with a minimum metric.
A state shown in the trellis diagram is expressed by a number representing different binary values output by shift registers serving as the delay elements 51, 52 and 53 employed in the convolution encoder shown in FIG. 1. Since such a number can have 8 (=23) different values, 8 different states can be represented by the number. In the following description, the 3 binary values are arranged in the following order: the delay element 53 followed by the delay element 52 followed by the delay element 51. For example, assume that the delay elements 53 and 52 output the binary value of 0 whereas the delay element 51 outputs the binary value of 1. In this case, the number representing 3 binary values output by the delay elements 51, 52 and 53 is “001”. If input data of 0 is received by the convolution encoder shown in FIG. 1 in a state of “000”, the encoder transits to the same state of “000”. If input data of 1 is received by the convolution encoder in a state of “000”, on the other hand, the encoder transits to a state of “001”.
In FIG. 2, notations x0 to x2 each denote a point of time. At the time x0, the state is “000”. At the time x1 following the time x0, the convolution encoder transits to another state of “000” or “001” due to input data of 0 or 1 respectively. By the same token, at the time x2 following the time x1, the convolution encoder transits from the other state “000” to a further state “000” or “001” due to further input data of 0 or 1 respectively, or from the other state of “001” to a further state of “010” or “011” due to further input data of 0 or 1 respectively.
On the other hand, the decoder computes a metric based on a received word or received data for each of paths through which such state transitions occur. A path with a minimum cumulated metric, that is, a path with a maximum likelihood, is selected as a probable path.
In a trellis computation carried out in a process to decode a data train completing such convolution encoding, a metric value obtained as a result of computation carried out at an immediately preceding point of time is read out from a memory such as a RAM or a register and used for computation of a metric value for the present point of time. A metric value obtained as a result of the computation carried out at the present point of time is then stored in the memory.
It should be noted that, in an embodiment described in this specification, pre-encoding input data, which should be the same as a final decoding result, is processed in 2-bit units. A processing timing is defined as a point of time at which input data is subjected to 2-bit-unit processing. Let notation t denote a processing timing corresponding to the time x0 at which input data is received. In this case, the next processing time is (t+1) corresponding to the time x2 at which first 2 bits of input data have been processed.
FIG. 3 is a diagram showing a typical configuration of a decoding circuit for the conventional convolution encoder. FIG. 4 is a diagram showing a trellis diagram used in a decoding process carried out by the decoding circuit with the configuration shown in FIG. 3.
In the decoding circuit shown in FIG. 3, an input terminal 201 receives data completing a convolution encoding process. The received data has been demodulated before being supplied to the input terminal 201. The received data is passed on to a computation unit 220. A control unit 210 includes a state-metric-memory control unit 211, a path-metric-memory control unit 212 and a trellis-computation-processing control unit 213. The state-metric-memory control unit 211 controls operations to write data into and read out data from a state-metric memory 240. On the other hand, the state-metric-memory control unit 212 controls operations to write data into and read out data from a path-metric memory 250. The trellis-computation-processing control unit 213 controls trellis computation processing carried out in the computation unit 220 and a result-outputting unit 230. A metric value obtained as a computation result output by the computation unit 220 is supplied to the state-metric memory 240 to be stored at an address in the state-metric memory 240 in a write operation controlled by a control signal generated by the state-metric-memory control unit 211 employed in the control unit 210. On the other hand, a metric value read out from an address in the state-metric memory 240 in a read operation controlled by a control signal generated by the state-metric-memory control unit 211 is supplied to the computation unit 220. Survival-path information obtained as a computation result output by the computation unit 220 is supplied to the result-outputting unit 230 in accordance with a control signal generated by the trellis-computation-processing control unit 213 employed in the control unit 210. The result-outputting unit 230 supplies a path-metric value after an operation to update information on a survival path to the path-metric memory 250 in accordance with a control signal generated by the trellis-computation-processing control unit 213. As described above, the path-metric-memory control unit 212 employed in the control unit 210 generates a control signal for controlling operations to write data into and read out data from an address in the path-metric memory 250. A path-metric value prior to an operation to update information on a survival path is read out from the path-metric memory 250 and supplied to the result-outputting unit 230. The result-outputting unit 230 outputs a final result of decoding to an output terminal 202 in accordance with a control signal generated by the trellis-computation-processing control unit 213 employed in the control unit 210.
Trellis processing computation processing operations carried out by the decoding circuit having the configuration shown in FIG. 3 are explained by referring to FIG. 4. FIG. 4 is a diagram showing data stored in the state-metric memory 240 employed in the decoding circuit shown in FIG. 3. For a constraint length of 4, there are 8 different states, namely, states S0 to S7. Metric values of states S0 to S7 are stored in the state-metric memory 240 at memory addresses MA0 to MA7 respectively. As described above, a time unit of the trellis computation processing corresponds to the period of 2 bits of pre-encoding data. That is to say, input data is subjected to the trellis computation processing with processing timings separated from each other by an interval corresponding to the period of the 2 bits.
As shown in FIG. 4, a time t corresponding to the processing timing is incremented by 1. As explained earlier with reference to FIG. 2, there are 4 different states such as S0 to S3 to which the convolution encoder can transit from a state such as S0 in a processing unit. As shown in FIG. 4, processing A is required for independently computing a metric value based on transitions from states S0, S2, S4 and S6 at a time (t−1) for state S0 at the time t. By the same token, processing B is carried out independently to compute a metric value based on transitions from states S0, S2, S4 and S6 at a time (t−1) for state S1 at the time t. In the same way, pieces of processing C to H are carried out independently of each other to compute metric values based on transitions from states S0, S2, S4 and S6 at a time (t−1) for respectively states S2 to S7 at the time t. Also in a transition from the time t to a time (t+1), the pieces of processing A to D are carried out independently of each other to compute metric values based on transitions from states S0, S2, S4 and S6 at a time t for respectively states S0, S1, S2 and S3 at the time (t+1). By the same token, in the transition from the time t to a time (t+1), the pieces of processing E to H are carried out independently of each other to compute metric values based on transitions from states S1, S3, S5 and S7 at a time t for respectively states S4, S5, S6 and S7 at the time (t+1).
By the way, in the conventional decoding circuit for decoding a signal completing a convolution encoding process as described above, as many pieces of mutually independent computation processing as states are required in the trellis computation. As described above, the number of states is determined in accordance with the constraint length. In the case of a constraint length of 4, for example, the number of states is determined to be 8. Since many pieces of such processing are required, there is raised a problem that it takes time to carry out the decoding process so that the frequency of a clock signal used in the decoding process needs to be increased.